package algorithm;

public class leetcode_0084 {
    public int largestRectangleArea(int[] heights) {
        int len=heights.length;
        int[] left=new int[len];
        int[] right=new int[len];
        int max=0;
        for(int i=0;i<len;++i){
            right[i]=len;
            left[i]=-1;
        }
        int [] stack=new int[len];
        int current=0;
        for(int i=0;i<len;++i){
            if(current==0||heights[i]>=heights[stack[current-1]]){
                stack[current]=i;
                current++;
            }
            else{
                while(current>=1&&heights[i]<heights[stack[current-1]]){
                    right[stack[current-1]]=i;
                    current--;
                }
                stack[current]=i;
                current++;
            }
        }
        current=0;
        for(int i=len-1;i>=0;--i){
            if(current==0||heights[i]>=heights[stack[current-1]]){
                stack[current]=i;
                current++;
            }
            else{
                while(current>=1&&heights[i]<heights[stack[current-1]]){
                    left[stack[current-1]]=i;
                    current--;
                }
                stack[current]=i;
                current++;
            }
        }
        for(int i=0;i<len;++i){
            max=Math.max(max,heights[i]*(right[i]-left[i]-1));
        }
        return max;
    }
}
